#include <iostream> 
#include <fstream> 
#include <cmath> 
#include <algorithm> 
#include <cassert> 
#include <string> 
#include <cstdlib> 
#include <cstdio> 
#include <vector> 
#include <map> 
#include <set> 
#include <ctime>

#define itn int 
#define float long double 
#define LL long long
#define pb push_back
#define mp make_pair

using namespace std;

const int base = 1000000009;
const int key = 239;

int hash(const string & s){
	LL result = 0;
	for (int i = 0; i < s.length(); i++){
		result = (result * key + s[i]) % base;
	}
	return result;
}

void max_common_subsequence(const vector<string> & first, const vector<string> & second, int & index1, int & index2, int upper_bound_1, int upper_bound_2){
	while (index1 < upper_bound_1 && index2 < upper_bound_2 && first[index1] == second[index2]){
		index1++;
		index2++;
	}
}

void max_common_subsequence_back(const vector<string> & first, const vector<string> & second, int & index1, int & index2, int lower_bound_1, int lower_bound_2){
	while (index1 > lower_bound_1 && index2 > lower_bound_2 && first[index1 - 1] == second[index2 - 1]){
		index1--;
		index2--;
	}
}

string find_changes(const vector<string> & first, const vector<string> & second, int lower_bound_1, int upper_bound_1, int lower_bound_2, int upper_bound_2, int D){

	if (D == 0){
		string result = "";
		for (int i = lower_bound_1; i < upper_bound_1; i++) result += '\\';
		return result;
	}
	if (upper_bound_1 == lower_bound_1){
		string result = "";
		for (int i = lower_bound_2; i < upper_bound_2; i++) result += '-';
		return result;
	}
	if (upper_bound_2 == lower_bound_2){
		string result = "";
		for (int i = lower_bound_1; i < upper_bound_1; i++) result += '|';
		return result;
	}
	if (D == 1){
		int x = lower_bound_1, y = lower_bound_2;
		string result = "";
		while (x < upper_bound_1 && y < upper_bound_2 && first[x] == second[y]){
			result += '\\';
			x++;
			y++;
		}
		if (upper_bound_1 - lower_bound_1 < upper_bound_2 - lower_bound_2){
			result += '-';
			y++;
		} else {
			result += '|';
			x++;
		}
		while (x < upper_bound_1){
			result += '\\';
			x++;
		}
		return result;
	}
	vector<pair<int, int> > a((D + 3) / 2), b((D + 3) / 2), c((D + 3) / 2);
	for (int d = 0; d <= (D + 1) / 2; d++){
		for (int i = 0; i <= d; i++){
			if (d == 0){
				int x = lower_bound_1, y = lower_bound_2;
                max_common_subsequence(first, second, x, y, upper_bound_1, upper_bound_2);
				a[i] = mp(x, y);
			} else {
				a[i] = mp(0, 0);
				pair<int, int> p;
				if (i < d){
					p = b[i];
					p.first++;
					max_common_subsequence(first, second, p.first, p.second, upper_bound_1, upper_bound_2);
					if (a[i].first < p.first || a[i].second < p.second) a[i] = p;
				}
				if (i > 0){
					p = b[i - 1];
					p.second++;
					max_common_subsequence(first, second, p.first, p.second, upper_bound_1, upper_bound_2);
					if (a[i].first < p.first || a[i].second < p.second) a[i] = p;
				}
			}
		}
		swap(a, b);
	}
	swap(a, b);
	for (int d = 0; d <= D / 2; d++){
		for (int i = 0; i <= d; i++){
			if (d == 0){
				int x = upper_bound_1, y = upper_bound_2;
				max_common_subsequence_back(first, second, x, y, lower_bound_1, lower_bound_2);
				c[i] = mp(x, y);
			} else {
				c[i] = mp(upper_bound_1, upper_bound_2);
				pair<int, int> p;
				if (i < d){
					p = b[i];
					p.second--;
					max_common_subsequence_back(first, second, p.first, p.second, lower_bound_1, lower_bound_2);
					if (c[i].first > p.first || c[i].second > p.second) c[i] = p;
				}
				if (i > 0){
					p = b[i - 1];
					p.first--;
					max_common_subsequence_back(first, second, p.first, p.second, lower_bound_1, lower_bound_2);
					if (c[i].first > p.first || c[i].second > p.second) c[i] = p;
				}
			}
		}
		swap(c, b);
	}
	swap(c, b);
	int mm = 0;
	for (int i = 0; i <= (D + 1) / 2; i++){
		if (2 * i + (upper_bound_1 - lower_bound_1) - (upper_bound_2 - lower_bound_2) - D % 2 >= 0 && 2 * i + (upper_bound_1 - lower_bound_1) - (upper_bound_2 - lower_bound_2) - D % 2 <= D + (D + 1) % 2 && a[i].first >= c[(2 * i + (upper_bound_1 - lower_bound_1) - (upper_bound_2 - lower_bound_2) - D % 2) / 2].first) mm = i;
	}
	return find_changes(first, second, lower_bound_1, a[mm].first, lower_bound_2, a[mm].second, (D + 1) / 2) + find_changes(first, second, a[mm].first, upper_bound_1, a[mm].second, upper_bound_2, D / 2);
}

void readall(ifstream & in, vector<string> & data){
	for (string line; getline(in, line); ){
		data.push_back(line);
	}
}

// @review: Нужно реализовать программу принимающую на вход пару файлов
// @review: и печатающую последовательность исправлений превращающий один файл
// @review: в другой.
// @review:
// @review: # diff file1.txt file2.txt
// @review: -Omfg, look at my code!
// @review:  My code is amazing!
// @review: -So... what do you want to do?
// @review: +Well, it's not really amazing.
// @review: +To be honest, it's not very beautiful code
// @review: +I should do anything else except coding
// @review:  May be eat?
// @review:  Possibly sleep
// @review: -I don't know what to write here also
// @review: -Possibly nothing
// @review: +Or solve maths?
// @review: +Yeah, it'd be great

int get_answer(const vector<string> & s, const vector<string> & t, int n, int m){
	vector<pair<int, int> > a(m + n + 1), b(m + n + 1);
	int answer = -1;
	for (int d = 0; d <= m + n && answer < 0; d++){
		for (int i = 0; i <= d && answer < 0; i++){
			if (d == 0){
				int x = 0, y = 0;
				max_common_subsequence(s, t, x, y, n, m);
				a[i] = mp(x, y);
			} else {
				a[i] = mp(0, 0);
				pair<int, int> p;
				if (i < d){
					p = b[i];
					p.second++;
					max_common_subsequence(s, t, p.first, p.second, n, m);
					if (a[i].first < p.first || a[i].second < p.second) a[i] = p;
				}
				if (i > 0){
					p = b[i - 1];
					p.first++;
					max_common_subsequence(s, t, p.first, p.second, n, m);
					if (a[i].first < p.first || a[i].second < p.second) a[i] = p;
				}
			}
			if (a[i].first == n && a[i].second == m){
				answer = d;
				break;
			}
		}
		swap(a, b);
	}
	return answer;
}

int main(){ 
	
	clock_t start = clock();
	
	ifstream F1("file1.txt");
	ifstream F2("file2.txt");
	
	vector<string> s, t;
	readall(F1, s);
	readall(F2, t);
	int n = s.size();
	int m = t.size();
	F1.close();
	F2.close();

	int answer = get_answer(s, t, n, m);
	
	ofstream out("result.txt");
	
//	out << answer << "\n";
	string res = find_changes(s, t, 0, n, 0, m, answer);
	int i = 0, j = 0;
	for (int _ = 0; _ < res.length(); _++){
		if (res[_] == '|') out << '-' << s[i++] << "\n"; else
		if (res[_] == '-') out << '+' << t[j++] << "\n"; else {
			out << s[i++] << "\n";
			j++;
		}
	}
	
	clock_t finish = clock();
	out << "----------------------\nTotal work time is about " << (int)(finish - start) << " ticks or " << (int)(finish - start) / CLOCKS_PER_SEC << " seconds\n";
	
	out.close();
	
	return 0; 
} 
